package niuke.week4;

import java.util.HashMap;
import java.util.Scanner;

/**
 已知一个消息流会不断地吐出整数，但不一定按照顺序吐出。
 如果上次打印的数为i，那么当i+1出现时，请打印i+1及其之后接收过的并且连续的所有数，直到全部接收并打印完


 */


public class MessPrint {
    Node head;
    HashMap<Integer,Node> headMap;
    HashMap<Integer,Node> tailMap;
    int waitNumber;
    int curNumber;

    public MessPrint() {
        headMap = new HashMap<>();
        tailMap = new HashMap<>();
        waitNumber = 1;
    }

    class Node{
        Node next;
        Node pre;
        int number;

        public Node(int number) {
            this.number = number;
        }
    }


    public void receive(int message){
        curNumber = message;
        Node curNode = new Node(message);
        headMap.put(message,curNode);
        tailMap.put(message,curNode);

        if(tailMap.containsKey(message-1)){
            Node preNode = tailMap.get(message - 1);
            preNode.next =curNode;
            curNode.pre = preNode;
            headMap.remove(curNode.number);//在头去掉当前节点
            tailMap.remove(preNode.number);//在尾去掉前一个节点
        }

        if(headMap.containsKey(message+1)){
            Node nextNode = headMap.get(message + 1);
            nextNode.pre =curNode;
            curNode.next = nextNode;
            tailMap.remove(curNode.number);//在尾去掉当前节点
            headMap.remove(nextNode.number);//在头去掉后一个节点
        }

        if(waitNumber == message){
            printMessage();
        }

    }

    public void printMessage(){
        Node node = headMap.get(waitNumber);
        headMap.remove(waitNumber);
        while (node!=null){
            System.out.println(node.number+" "+ curNumber);
            waitNumber++;
            node = node.next;
        }
        tailMap.remove(waitNumber-1);
    }

    public static void main(String[] args) {
        MessPrint messPrint = new MessPrint();
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        for (int i = 0; i < number; i++) {
            messPrint.receive(sc.nextInt());
        }
    }
}

